"""
二型文法转格雷巴赫范式 Greibach normal form

格雷巴赫范式 只有如下两种形式的产生式：
A->a (仅一个终结符）
A->aA1A2......Am (仅开头一个终结符，其他均为非终结符)
"""
import collections
import re
from GNF import CFG_to_GNF


def Reduced_sorted_Grammar(Path, S):
    V, T, P, S = CFG_to_GNF.reduceGrammar(Path, S)  # 获取化简过的二型文法
    var_to_An = collections.defaultdict()
    for i, var in enumerate(V):
        var_to_An[var] = ('A' + str(i + 1), 'A', i + 1, 'Variable')  # An的n从1开始

    resP = collections.defaultdict(list)
    for left, rights in P.items():
        for right in rights:
            tmp = []
            for symbol, attr in right:
                if attr == 'Variable':
                    tmp.append(var_to_An[symbol])
                if attr == 'Terminal':
                    tmp.append((symbol, symbol, 0, 'Terminal'))
            newLeft = var_to_An[left][0]
            resP[newLeft].append(tmp)

    resS = var_to_An[S][0]
    resV = set()
    for var in V:
        resV.add(var_to_An[var][0])
    # print(resP)
    return resV, T, resP, resS


def showProductions(P: collections.defaultdict(list)):
    print('________________showProductions_______________')
    for left, rights in P.items():
        # print(left, 'right num:', len(rights))

        production = left + ' -> '
        for i, right in enumerate(rights):
            production += ''.join([s + ' ' for s, n, id, attr in right])
            if i < len(rights)-1:
                production += '| '
            # print(''.join([s + ' ' for s, attr in right]))

        print(production, '\n')


class NewVariable:

    def __init__(self, init_num=1):
        self.cnt = init_num

    def get_new_var(self):
        new_var = ('NewVariable' + str(self.cnt), 'NewVariable', self.cnt, 'Variable')
        self.cnt += 1
        return new_var


factory = NewVariable(1)


def isGNF(right: list):
    if right[0][3] != 'Terminal':
        return False

    for symbol, name, id, attr in right[1:]:
        if attr == 'Terminal':
            return False

    return True


def read_file(file_path):
    # V = set()
    # T = set()
    # S = None
    P = collections.defaultdict(list)
    with open(file_path, 'r') as f:
        for line in f.readlines():
            line = line.strip('\n').split()
            print(line)

            # 针对单个产生式
            left = None
            right = []
            for i, symbol in enumerate(line):  # A1 -> A2
                name = re.sub(r'\d', '', symbol)
                id = re.sub(r'\D', '', symbol)
                id = int(id) if id else 0  # 其他下标要从1开始
                if i == 0:
                    left = symbol
                if i == 1:  # 忽略'->'
                    continue
                if i >= 2:
                    if str(name).islower():
                        right.append((symbol, name, id, 'Terminal'))
                        # T.add(symbol)
                    elif str(name).isupper():
                        right.append((symbol, name, id, 'Variable'))
                        # V.add(symbol)
            P[left].append(right)

    # print(P)
    return P


def first(P: collections.defaultdict(list)):
    P1 = collections.defaultdict(list)

    r2l = collections.defaultdict(tuple)  # 第一步中新生成的产生式 防止重复使用 比如 c 统一都变成 NewVariable1
    for left, rights in P.items():
        for idx, right in enumerate(rights):
            # print(right)
            if isGNF(right):
                # 满足GNF要求就不用管
                P1[left].append(right)
                # print('isGNF')
            else:
                # print('notGNF')
                # 首先这个产生式不满足要求 需要修改 先将其去除
                # P[left].pop(idx) 因为是将修改过的加入新的P1 所以这里不用去除 而且直接pop会导致循环的错误

                # 修改这个产生式 把其中
                for sym_idx, (symbol, name, id, attr) in enumerate(right):
                    if sym_idx == 0: continue  # 修改对于第一个字符没有要求

                    if attr == 'Terminal':
                        if symbol in r2l:
                            right[sym_idx] = r2l[symbol]
                        else:
                            newSym, newName, newID, newAttr = factory.get_new_var()
                            # 用新的变量替代原来的Terminal
                            right[sym_idx] = (newSym, newName, newID, newAttr)
                            r2l[symbol] = (newSym, newName, newID, newAttr)
                            # 将新的产生式加入P1
                            P1[newSym].append([(symbol, name, id, attr)])

                # print('new right:', right)
                # 将修改好的产生式加入P1
                P1[left].append(right)

    # print(P1)
    return P1


"""
第一阶段处理结束以后 产生式中存在的只有：
1.满足GNF的式子 A->a (仅一个终结符）A->aA1A2......Am (仅开头一个终结符，其他均为非终结符)
2.A->A1 A2 A2 (后面全是非终结符的式子）
"""

"""
书中一开输入的文法 除了终结符 其余的非终结符都是An的形式
An的形式和使用A，B，C...之类的是等价的 符号之间都是可以相互区分的
将输入文法的非终结符都变为An的好处在于 An增加了n这个数字 作为标记 方便在后面的处理循环 
比如 A->B B->C C->A 变为 A1->A2 A2->A3 A3->A1 通过要求Ak->Aj中的j>=k 使产生式带入 会阻断循环
变为 A1->A2 A2->A3 A3->A3(A1->A2->A3)

至于算法中新引入的非终结符是否需要以An的形式存在 个人感觉应该都可以
因为引入新非终极符 在于第一步 和第二步的处理左递归 并不会产生循环
"""


def is_i_greater_j(left, right):
    left_name = re.sub(r'\d', '', left)
    left_id = re.sub(r'\D', '', left)
    left_id = int(left_id) if id else 0
    if left_name == right[0][1] and left_id > right[0][2]:
        return True
    return False


def is_i_eq_j(left, right):
    left_name = re.sub(r'\d', '', left)
    left_id = re.sub(r'\D', '', left)
    left_id = int(left_id) if id else 0
    if left_name == right[0][1] and left_id == right[0][2]:
        return True
    return False


def is_i_less_j(left, right):
    left_name = re.sub(r'\d', '', left)
    left_id = re.sub(r'\D', '', left)
    left_id = int(left_id) if id else 0
    if left_name == right[0][1] and left_id < right[0][2]:
        return True
    return False


def second(P1: collections.defaultdict(list)):
    P2 = collections.defaultdict(list)

    queue_kj = collections.deque()  # 用于第二部分的第一步处理 让 Ak->Aj(k<=j)
    left_recursion = collections.defaultdict(list)  # 用于第二部分的第二步处理 解决左递归的问题
    # 左边一致的左递归 可以一并解决

    # 把符合GNF的产生式直接加入P2
    for left, rights in P1.items():
        for right in rights:
            if isGNF(right):
                P2[left].append(right)
            else:
                queue_kj.append((left, right))
    """
    ↓↓↓↓↓↓↓↓↓↓↓↓
    剩下的式子都是 A->A1 A2 A2 (后面全是非终结符的式子）
    Ai->Aj
    （符合GNF都可以加入P2）
    1. 如果 i<j 符合要求就加入P2
    2. 如果 i==j 就要解决左递归 就要加入queue_recursion
    3. 如果 i>j 就要进行替换
    """
    # 解决Ak->Aj(j<k)
    while queue_kj:
        left, right = queue_kj.popleft()

        if isGNF(right):
            P2[left].append(right)
        elif is_i_less_j(left, right):
            P2[left].append(right)
        elif is_i_eq_j(left, right):
            left_recursion[left].append(right)
        else:
            Aj = right[0][0]
            for Aj_right in P1[Aj]:
                queue_kj.append((left, Aj_right + right[1:]))

    # print('P2:', P2)
    # print('recursion:', left_recursion)
    """
    此时 P2中存储的就是Ak的非左递归产生式
    而 queue_recursion中是Ak的递归产生式
    """
    for left, rights in left_recursion.items():
        # 需要引入一个新的变量来解决左递归
        newSym, newName, newID, newAttr = factory.get_new_var()

        # for right in P2[left]:
        #     P2[left].append(right+[(newSym, newName, newID, newAttr)])
        # 这样写 将新的式子又加入到P2中 导致无线循环
        tmp = [right + [(newSym, newName, newID, newAttr)] for right in P2[left]]
        P2[left] += tmp

        for right in rights:
            P2[newSym].append(right[1:])

        for right in rights:
            P2[newSym].append(right[1:] + [(newSym, newName, newID, newAttr)])

    # print('P2:', P2)
    return P2


def all_is_GNF(rights):
    for right in rights:
        if not isGNF(right):
            return False
    return True


"""
到底怎么将满足要求GNF带入到其他式子中 使其他式子满足GNF
思路混乱 导致代码混乱
按照书上的方式 应该是由An向A1逐步推进
然后再搞定B1
"""

"""
先实现An的往回代入，再实现其他新变量的代入是完备的
因为An中只有两种变量一种是A（反向代入也是满足GNF） 一种是第一步产生的新变量（满足GNF）
"""


def third(P2: collections.defaultdict(list), max_n):
    P3 = collections.defaultdict(list)

    """
    从An开始逐步往回代入
    """
    for i in range(max_n, 0, -1):
        symbol = 'A' + str(i)
        # print('___________', symbol, '________________')
        for right in P2[symbol]:
            # print(right)
            if isGNF(right):
                P3[symbol].append(right)
                # print('is GNF append')
            else:
                # print('not GNF')
                sym, name, id, attr = right[0]
                for r in P3[sym]:  # 要从P3中选择产生式代入 因为P3中是已经确定好的GNF 才可以代入
                    P3[symbol].append(r + right[1:])
                    # print('append', r + right[1:])

    """
    接着处理 为解决左递归而引入的新变量
    """
    for left, rights in P2.items():
        if 'A' in left:
            continue

        for right in rights:
            if isGNF(right):
                P3[left].append(right)
            else:
                sym, name, id, attr = right[0]
                for r in P3[sym]:
                    P3[left].append(r + right[1:])

    # print(P3)
    return P3


"""
因为实现了Ak->Aj(k<j)
最终的压力都来到最后的An 
在逐步递推到An->An这一步时 不断的收集An->GNF
最后An的产生式只有两种
1. 满足GNF的式子
2. 一种是递归的式子
递归的式子 可以转化为非递归的式子 然后由此An就只有满足GNF的产生式 然后再反推出A1 A2的满足GNF的产生式
最后再处理 解决递归过程中产生的新变量的GNF问题
"""


def getGNF(path='D:\\p.txt', S='S'):
    V, T, P, S = Reduced_sorted_Grammar(path, S=S)
    P1 = first(P)
    P2 = second(P1)
    P3 = third(P2, len(V))

    return V, T, P3, S


if __name__ == '__main__':
    # path = 'D:\\p.txt'
    path = 'p3.txt'
    V, T, P, S = Reduced_sorted_Grammar(path, S='S')

    # file_path = 'D:\\productions.txt'
    # P = read_file(file_path)

    P1 = first(P)
    P2 = second(P1)
    P3 = third(P2, len(V))
    print('对应的格雷巴赫范式：')
    showProductions(P3)
